/*
 * @lc app=leetcode.cn id=221 lang=cpp
 *
 * [221] 最大正方形
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int maximalSquare(vector<vector<char>> &matrix)
    {
        const int M = matrix.size();
        const int N = matrix[0].size();

        vector<vector<int>> dp(
            M, vector<int>(N, 0));

        int ans = 0;

        for (int i = 0; i < M; i++)
            if (matrix[i][0] == '1')
            {
                dp[i][0] = 1;
                ans = 1;
            }
        for (int j = 0; j < N; j++)
            if (matrix[0][j] == '1')
            {
                dp[0][j] = 1;
                ans = 1;
            }

        for (int i = 1; i < M; ++i)
        {
            for (int j = 1; j < N; ++j)
            {
                if (matrix[i][j] == '1')
                {
                    dp[i][j] = 1 + std::min(
                                       std::min(dp[i - 1][j], dp[i][j - 1]),
                                       dp[i - 1][j - 1]);
                    
                    ans = std::max(ans, dp[i][j]);
                }
            }
        }

        return ans * ans;
    }
};
// @lc code=end
